﻿// An Alternative implementation of Generic Dictionary Class
// Author: Zhenyu Wu
// Email: Zhenyu.5Wu@gmail.com

Unit JumboDictionary;

// Adaptive split works by splitting the keyspace according to the distribution range of key values.
// Note that, if the hash function is performing reasonably, turning on this feature should not bring
// any performance benefit. However, if you suspect for some reason the hash function is clustering
// hash values, use this feature can help get a more efficient key space partitioning.
{.$DEFINE AdaptiveSplit}

Interface

 Uses
  SysUtils, Classes,
  Generics.Collections,
  Generics.Defaults;

 Type
  TJumboDictionary<TKey, TValue> = Class(TEnumerable<TPair<TKey, TValue>>)
   Private Const
    DefSplitThreshold = 8;

   Private Type
    PEntryItem = ^TEntryItem;

    TEntryItem = Record
     JumboHash: Cardinal;
     Next: PEntryItem;
     Key: TKey;
     Value: TValue;
    END;

    PEntrySlot = ^TEntrySlot;

    TEntrySlot = Record
     HashMarker: Cardinal;
{$IFDEF AdaptiveSplit}
     Range: Cardinal;
{$ENDIF AdaptiveSplit}
     ItemHead: PEntryItem;
     Next: PEntrySlot;
     Up, Down: PEntrySlot;
    END;

   Private
    EntryHead: PEntrySlot;
    FCount: Integer;
    FComparer: IEqualityComparer<TKey>;
    FSplitThreshold: Cardinal;
    FLookupTable: Array [Word] of PEntrySlot;

    Function Hash(Const Key: TKey): Cardinal;
    Function SplitSlot(Const Slot: PEntrySlot): PEntrySlot;
    Function GetSlot(Const HashValue: Cardinal): PEntrySlot;
    Function SlotGetItem(Var Slot: PEntrySlot; Const Key: TKey): PEntryItem;
    Function SlotInitItem(Const Slot: PEntrySlot): PEntryItem;
    Procedure SlotRemoveItem(Var Slot: PEntrySlot; Const Item: PEntryItem);

    Function GetItem(Const Key: TKey): TValue;
    Procedure SetItem(Const Key: TKey; Const Value: TValue);

    Procedure DoAdd(Const Item: PEntryItem; Const Key: TKey; Const Value: TValue);
    Procedure DoSetValue(Const Item: PEntryItem; Const Value: TValue);
    Procedure DoRemove(Const Item: PEntryItem; Notification: TCollectionNotification);

   Protected
    Function DoGetEnumerator: TEnumerator<TPair<TKey, TValue>>; Override;
    Procedure KeyNotify(Const Key: TKey; Action: TCollectionNotification); Virtual;
    Procedure ValueNotify(Const Value: TValue; Action: TCollectionNotification); Virtual;

   Public
    Constructor Create(Const SplitThreshold: Cardinal = DefSplitThreshold); Overload;
    Constructor Create(Const AComparer: IEqualityComparer<TKey>; Const SplitThreshold: Cardinal = DefSplitThreshold); Overload;
    Constructor Create(Collection: TEnumerable<TPair<TKey, TValue>>; Const AComparer: IEqualityComparer<TKey>; Const SplitThreshold: Cardinal = DefSplitThreshold); Overload;
    Destructor Destroy; Override;

    Procedure Add(Const Key: TKey; Const Value: TValue);
    Procedure Remove(Const Key: TKey);
    Function ExtractPair(Const Key: TKey): TPair<TKey, TValue>;
    Procedure Clear(Const TearDown: Boolean = False);
    Function TryGetValue(Const Key: TKey; Out Value: TValue): Boolean;
    Procedure AddOrSetValue(Const Key: TKey; Const Value: TValue);
    Function ContainsKey(Const Key: TKey): Boolean;
    Function ContainsValue(Const Value: TValue): Boolean; Overload;
    Function ContainsValue(Const Value: TValue; AComparer: IEqualityComparer<TValue>): Boolean; Overload;

    Property Items[Const Key: TKey]: TValue read GetItem write SetItem; Default;
    Property Count: Integer read FCount;

   Type
    TPairEnumerator = Class(TEnumerator<TPair<TKey, TValue>>)
     Private
      EntrySlot: PEntrySlot;
      EntryItem: PEntryItem;
      Function GetCurrent: TPair<TKey, TValue>;

     Protected
      Function DoGetCurrent: TPair<TKey, TValue>; Override;
      Function DoMoveNext: Boolean; Override;

     Public
      Constructor Create(ADictionary: TJumboDictionary<TKey, TValue>);
      Property Current: TPair<TKey, TValue>read GetCurrent;
      Function MoveNext: Boolean;
    END;

    TKeyEnumerator = Class(TEnumerator<TKey>)
     Private
      EntrySlot: PEntrySlot;
      EntryItem: PEntryItem;
      Function GetCurrent: TKey;

     Protected
      Function DoGetCurrent: TKey; Override;
      Function DoMoveNext: Boolean; Override;

     Public
      Constructor Create(ADictionary: TJumboDictionary<TKey, TValue>);
      Property Current: TKey read GetCurrent;
      Function MoveNext: Boolean;
    END;

    TValueEnumerator = Class(TEnumerator<TValue>)
     Private
      EntrySlot: PEntrySlot;
      EntryItem: PEntryItem;
      Function GetCurrent: TValue;

     Protected
      Function DoGetCurrent: TValue; Override;
      Function DoMoveNext: Boolean; Override;

     Public
      Constructor Create(ADictionary: TJumboDictionary<TKey, TValue>);
      Property Current: TValue read GetCurrent;
      Function MoveNext: Boolean;
    END;

    TValueCollection = Class(TEnumerable<TValue>)
     Private
      FDictionary: TJumboDictionary<TKey, TValue>;
      Function GetCount: Integer;

     Protected
      Function DoGetEnumerator: TEnumerator<TValue>; Override;

     Public
      Constructor Create(ADictionary: TJumboDictionary<TKey, TValue>);
      Function GetEnumerator: TValueEnumerator; Reintroduce;
      Property Count: Integer read GetCount;
    END;

    TKeyCollection = Class(TEnumerable<TKey>)
     Private
      FDictionary: TJumboDictionary<TKey, TValue>;
      Function GetCount: Integer;

     Protected
      Function DoGetEnumerator: TEnumerator<TKey>; Override;

     Public
      Constructor Create(ADictionary: TJumboDictionary<TKey, TValue>);
      Function GetEnumerator: TKeyEnumerator; Reintroduce;
      Property Count: Integer read GetCount;
    END;

   Private
    FOnKeyNotify: TCollectionNotifyEvent<TKey>;
    FOnValueNotify: TCollectionNotifyEvent<TValue>;
    FKeyCollection: TKeyCollection;
    FValueCollection: TValueCollection;
    Function GetKeys: TKeyCollection;
    Function GetValues: TValueCollection;

   Public
    Function GetEnumerator: TPairEnumerator; Reintroduce;
    Property Keys: TKeyCollection read GetKeys;
    Property Values: TValueCollection read GetValues;
    Property OnKeyNotify: TCollectionNotifyEvent<TKey>read FOnKeyNotify write FOnKeyNotify;
    Property OnValueNotify: TCollectionNotifyEvent<TValue>read FOnValueNotify write FOnValueNotify;
  END;

Implementation

 Uses
  RTLConsts;

 { TJumboDictionary<TKey, TValue> }

 Constructor TJumboDictionary<TKey, TValue>.Create(Collection: TEnumerable<TPair<TKey, TValue>>; Const AComparer: IEqualityComparer<TKey>; Const SplitThreshold: Cardinal);
  Var
   Item: TPair<TKey, TValue>;
  BEGIN
   Create(AComparer, SplitThreshold);

   For Item in Collection do
    AddOrSetValue(Item.Key, Item.Value);
  END;

 Constructor TJumboDictionary<TKey, TValue>.Create(Const AComparer: IEqualityComparer<TKey>; Const SplitThreshold: Cardinal);
  Var
   Index: Cardinal;
  BEGIN
   Inherited Create;

   FSplitThreshold:= SplitThreshold;
   FComparer:= AComparer;
   IF FComparer = NIL then
    FComparer:= TEqualityComparer<TKey>.Default;

   New(EntryHead);
   FillChar(EntryHead^, Sizeof(TEntrySlot), 0);

   For Index:= 0 to $FFFF do
    FLookupTable[Index]:= EntryHead;
  END;

 Constructor TJumboDictionary<TKey, TValue>.Create(Const SplitThreshold: Cardinal);
  BEGIN
   Create(NIL, SplitThreshold);
  END;

 Destructor TJumboDictionary<TKey, TValue>.Destroy;
  BEGIN
   Clear(True);
   Dispose(EntryHead);
   FKeyCollection.Free;
   FValueCollection.Free;

   Inherited;
  END;

 Procedure TJumboDictionary<TKey, TValue>.Add(Const Key: TKey; Const Value: TValue);
  Var
   HashValue: Cardinal;
   EntrySlot: PEntrySlot;
   EntryItem: PEntryItem;
  BEGIN
   HashValue:= Hash(Key);
   EntrySlot:= GetSlot(HashValue);
   EntryItem:= SlotGetItem(EntrySlot, Key);

   IF NOT Assigned(EntryItem) then
    EntryItem:= SlotInitItem(EntrySlot)
   else // Check if item exists
    BEGIN
     IF (HashValue = EntryItem.JumboHash) AND FComparer.Equals(Key, EntryItem.Key) then
      Raise EListError.CreateRes(@SGenericDuplicateItem);
     New(EntryItem.Next);
     EntryItem:= EntryItem.Next;
     FillChar(EntryItem^, Sizeof(TEntryItem), 0);
    END;

   EntryItem.JumboHash:= HashValue;
{$IFDEF AdaptiveSplit}
   Dec(HashValue, EntrySlot.HashMarker);
   IF HashValue > EntrySlot.Range then
    EntrySlot.Range:= HashValue;
{$ENDIF AdaptiveSplit}
   EntryItem.Next:= NIL;
   DoAdd(EntryItem, Key, Value);
  END;

 Procedure TJumboDictionary<TKey, TValue>.AddOrSetValue(Const Key: TKey; Const Value: TValue);
  Var
   HashValue: Cardinal;
   EntrySlot: PEntrySlot;
   EntryItem: PEntryItem;
  BEGIN
   HashValue:= Hash(Key);
   EntrySlot:= GetSlot(HashValue);
   EntryItem:= SlotGetItem(EntrySlot, Key);

   IF NOT Assigned(EntryItem) then
    EntryItem:= SlotInitItem(EntrySlot)
   else // Check if item exists
    BEGIN
     IF (HashValue = EntryItem.JumboHash) AND FComparer.Equals(Key, EntryItem.Key) then
      BEGIN
       DoSetValue(EntryItem, Value);
       Exit;
      END;
     New(EntryItem.Next);
     EntryItem:= EntryItem.Next;
     FillChar(EntryItem^, Sizeof(TEntryItem), 0);
    END;

   EntryItem.JumboHash:= HashValue;
   EntryItem.Next:= NIL;
   DoAdd(EntryItem, Key, Value);
  END;

 Procedure TJumboDictionary<TKey, TValue>.Clear(Const TearDown: Boolean);
  Var
   Index: Cardinal;
   EntrySlot, OldSlot: PEntrySlot;
   EntryItem, OldItem: PEntryItem;
  BEGIN
   FCount:= 0;

   EntrySlot:= EntryHead;
   Repeat
    EntryItem:= EntrySlot.ItemHead;
    While Assigned(EntryItem) do
     BEGIN
      DoRemove(EntryItem, cnRemoved);
      OldItem:= EntryItem;
      EntryItem:= EntryItem.Next;

      OldItem.Key:= Default(TKey);
      OldItem.Value:= Default(TValue);
      Dispose(OldItem);
     END;

    IF Assigned(EntrySlot.Next) then
     BEGIN
      OldSlot:= EntrySlot;
      EntrySlot:= EntrySlot.Next;
      Dispose(OldSlot);
     END
    else
     Break;
   Until False;

   EntryHead:= EntrySlot;
   IF NOT TearDown then
    BEGIN
     FillChar(EntryHead^, Sizeof(TEntrySlot), 0);

     For Index:= 0 to $FFFF do
      FLookupTable[Index]:= EntryHead;
    END;
  END;

 Function TJumboDictionary<TKey, TValue>.ContainsKey(Const Key: TKey): Boolean;
  Var
   HashValue: Cardinal;
   EntrySlot: PEntrySlot;
   EntryItem: PEntryItem;
  BEGIN
   Result:= False;
   HashValue:= Hash(Key);
   EntrySlot:= GetSlot(HashValue);
   EntryItem:= SlotGetItem(EntrySlot, Key);

   IF Assigned(EntryItem) then
    Result:= (HashValue = EntryItem.JumboHash) AND FComparer.Equals(Key, EntryItem.Key);
  END;

 Function TJumboDictionary<TKey, TValue>.ContainsValue(Const Value: TValue): Boolean;
  BEGIN
   Result:= ContainsValue(Value, NIL);
  END;

 Function TJumboDictionary<TKey, TValue>.ContainsValue(Const Value: TValue; AComparer: IEqualityComparer<TValue>): Boolean;
  Var
   EntrySlot: PEntrySlot;
   EntryItem: PEntryItem;
  BEGIN
   Result:= False;
   IF NOT Assigned(AComparer) then
    AComparer:= TEqualityComparer<TValue>.Default;

   EntrySlot:= @EntryHead;
   Repeat
    EntryItem:= EntrySlot.ItemHead;
    While Assigned(EntryItem) do
     BEGIN
      IF AComparer.Equals(EntryItem.Value, Value) then
       Exit(True);
      EntryItem:= EntryItem.Next;
     END;
    EntrySlot:= EntrySlot.Next;
   Until NOT Assigned(EntrySlot);
  END;

 Procedure TJumboDictionary<TKey, TValue>.DoAdd(Const Item: PEntryItem; Const Key: TKey; Const Value: TValue);
  BEGIN
   Item.Key:= Key;
   Item.Value:= Value;
   Inc(FCount);

   KeyNotify(Key, cnAdded);
   ValueNotify(Value, cnAdded);
  END;

 Procedure TJumboDictionary<TKey, TValue>.DoRemove(Const Item: PEntryItem; Notification: TCollectionNotification);
  BEGIN
   KeyNotify(Item.Key, Notification);
   ValueNotify(Item.Value, Notification);
  END;

 Procedure TJumboDictionary<TKey, TValue>.DoSetValue(Const Item: PEntryItem; Const Value: TValue);
  Var
   OldValue: TValue;
  BEGIN
   OldValue:= Item.Value;
   Item.Value:= Value;

   ValueNotify(OldValue, cnRemoved);
   ValueNotify(Value, cnAdded);
  END;

 Function TJumboDictionary<TKey, TValue>.DoGetEnumerator: TEnumerator<TPair<TKey, TValue>>;
  BEGIN
   Result:= GetEnumerator;
  END;

 Function TJumboDictionary<TKey, TValue>.ExtractPair(Const Key: TKey): TPair<TKey, TValue>;
  Var
   HashValue: Cardinal;
   EntrySlot: PEntrySlot;
   EntryItem: PEntryItem;
  BEGIN
   Result:= TPair<TKey, TValue>.Create(Key, Default(TValue));
   HashValue:= Hash(Key);
   EntrySlot:= GetSlot(HashValue);
   EntryItem:= SlotGetItem(EntrySlot, Key);

   IF Assigned(EntryItem) then
    IF (HashValue = EntryItem.JumboHash) AND FComparer.Equals(Key, EntryItem.Key) then
     BEGIN
      Result.Value:= EntryItem.Value;
      DoRemove(EntryItem, cnExtracted);
      SlotRemoveItem(EntrySlot, EntryItem);
     END;
  END;

 Function TJumboDictionary<TKey, TValue>.GetEnumerator: TPairEnumerator;
  BEGIN
   Result:= TPairEnumerator.Create(Self);
  END;

 Function TJumboDictionary<TKey, TValue>.GetItem(Const Key: TKey): TValue;
  Var
   HashValue: Cardinal;
   EntrySlot: PEntrySlot;
   EntryItem: PEntryItem;
  BEGIN
   HashValue:= Hash(Key);
   EntrySlot:= GetSlot(HashValue);
   EntryItem:= SlotGetItem(EntrySlot, Key);

   IF Assigned(EntryItem) then
    IF (HashValue = EntryItem.JumboHash) AND FComparer.Equals(Key, EntryItem.Key) then
     Exit(EntryItem.Value);

   Raise EListError.CreateRes(@SGenericItemNotFound);
  END;

 Function TJumboDictionary<TKey, TValue>.GetKeys: TKeyCollection;
  BEGIN
   IF FKeyCollection = NIL then
    FKeyCollection:= TKeyCollection.Create(Self);
   Result:= FKeyCollection;
  END;

 Function TJumboDictionary<TKey, TValue>.GetSlot(Const HashValue: Cardinal): PEntrySlot;
  Var
   LastBase: PEntrySlot;
  BEGIN
   LastBase:= FLookupTable[HashValue SHR 16];
   Result:= LastBase;
   While Assigned(Result) do
    BEGIN
     IF Result.HashMarker = HashValue then
      Exit;

     IF Result.HashMarker > HashValue then
      Result:= Result.Down
     else // Move the safe base
      BEGIN
       // This is just a hack to prevent the worst case lookup
       // (but does not prevent the second worst, though... :P)
       IF NOT Assigned(Result.Next) OR (Result.Next.HashMarker > HashValue) then
        Exit;

       LastBase:= Result;
       Result:= Result.Up;
      END;
    END;

   Result:= LastBase;
  END;

 Function TJumboDictionary<TKey, TValue>.GetValues: TValueCollection;
  BEGIN
   IF FValueCollection = NIL then
    FValueCollection:= TValueCollection.Create(Self);
   Result:= FValueCollection;
  END;

 Function TJumboDictionary<TKey, TValue>.Hash(Const Key: TKey): Cardinal;
  BEGIN
   Result:= FComparer.GetHashCode(Key);
  END;

 Procedure TJumboDictionary<TKey, TValue>.KeyNotify(Const Key: TKey; Action: TCollectionNotification);
  BEGIN
   IF Assigned(FOnKeyNotify) then
    FOnKeyNotify(Self, Key, Action);
  END;

 Procedure TJumboDictionary<TKey, TValue>.Remove(Const Key: TKey);
  Var
   HashValue: Cardinal;
   EntrySlot: PEntrySlot;
   EntryItem: PEntryItem;
  BEGIN
   HashValue:= Hash(Key);
   EntrySlot:= GetSlot(HashValue);
   EntryItem:= SlotGetItem(EntrySlot, Key);

   IF Assigned(EntryItem) then
    IF (HashValue = EntryItem.JumboHash) AND FComparer.Equals(Key, EntryItem.Key) then
     BEGIN
      DoRemove(EntryItem, cnRemoved);
      SlotRemoveItem(EntrySlot, EntryItem);
     END;
  END;

 Procedure TJumboDictionary<TKey, TValue>.SetItem(Const Key: TKey; Const Value: TValue);
  Var
   HashValue: Cardinal;
   EntrySlot: PEntrySlot;
   EntryItem: PEntryItem;
  BEGIN
   HashValue:= Hash(Key);
   EntrySlot:= GetSlot(HashValue);
   EntryItem:= SlotGetItem(EntrySlot, Key);

   IF Assigned(EntryItem) then
    IF (HashValue = EntryItem.JumboHash) AND FComparer.Equals(Key, EntryItem.Key) then
     BEGIN
      DoSetValue(EntryItem, Value);
      Exit;
     END;

   Raise EListError.CreateRes(@SGenericItemNotFound);
  END;

 Function TJumboDictionary<TKey, TValue>.SlotGetItem(Var Slot: PEntrySlot; Const Key: TKey): PEntryItem;
  Var
   Trial: Cardinal;
   HashValue: Cardinal;
   NewSlot: PEntrySlot;
  BEGIN
   HashValue:= Hash(Key);
   Repeat
    Trial:= 0;
    Result:= Slot.ItemHead;
    IF NOT Assigned(Result) then
     Exit;

    While Assigned(Result.Next) do
     BEGIN
      IF (HashValue = Result.JumboHash) AND FComparer.Equals(Key, Result.Key) then
       Break;
      Result:= Result.Next;
      Inc(Trial);
     END;

    // Check if Trial count exceeds SplitThreshold
    IF Trial > FSplitThreshold then
     BEGIN
      NewSlot:= SplitSlot(Slot);
      IF Assigned(NewSlot) then
       BEGIN
        IF HashValue >= NewSlot.HashMarker then
         Slot:= NewSlot;
       END
      else
       Trial:= 0;
     END;
   Until Trial <= FSplitThreshold;
  END;

 Function TJumboDictionary<TKey, TValue>.SlotInitItem(Const Slot: PEntrySlot): PEntryItem;
  BEGIN
   New(Slot.ItemHead);
   Result:= Slot.ItemHead;
   FillChar(Result^, Sizeof(TEntryItem), 0);
  END;

 Procedure TJumboDictionary<TKey, TValue>.SlotRemoveItem(Var Slot: PEntrySlot; Const Item: PEntryItem);
  Var
   RemItem: PEntryItem;
  BEGIN
   IF Assigned(Item.Next) then
    BEGIN
     RemItem:= Item.Next;
     Item^:= Item.Next^;
    END
   else // Deleting tail
    BEGIN
     IF Slot.ItemHead = Item then
      Slot.ItemHead:= NIL
     else
      BEGIN
       RemItem:= Slot.ItemHead;
       While RemItem.Next <> Item do
        RemItem:= RemItem.Next;
       RemItem.Next:= NIL;
      END;
     RemItem:= Item;
    END;

   RemItem.Key:= Default(TKey);
   RemItem.Value:= Default(TValue);
   Dispose(RemItem);
  END;

 Function TJumboDictionary<TKey, TValue>.SplitSlot(Const Slot: PEntrySlot): PEntrySlot;
  Var
   Index, LTLow, LTHigh: Integer;
   Range: Cardinal;
   OldEntryItem, EntryItem: PEntryItem;
   NewEntryItem: PEntryItem;
  BEGIN
{$IFNDEF AdaptiveSplit}
   IF NOT Assigned(Slot.Next) then
    // Extends from here to infinity
    Range:= INFINITE - Slot.HashMarker
   else // Extends from here to the next slot
    Range:= Slot.Next.HashMarker - Slot.HashMarker - 1;
{$ELSE}
   Range:= Slot.Range;
{$ENDIF AdaptiveSplit}
   IF Range = 0 then
    Exit(NIL); // Cannot split anymore

   New(Result);
   FillChar(Result^, Sizeof(TEntrySlot), 0);
   Result.HashMarker:= (Range SHR 1) + Slot.HashMarker + 1;

   LTLow:= Result.HashMarker SHR 16;
   IF (Result.HashMarker AND $FFFF) <> 0 then
    Inc(LTLow);

   IF NOT Assigned(Slot.Next) then
    BEGIN
     Slot.Up:= Result; // New slot is the upward arc from here
     LTHigh:= $FFFF;
    END
   else
    BEGIN
     IF NOT Assigned(Slot.Next.Down) then
      // New slot is the downward arc of the next slot
      Slot.Next.Down:= Result
     else // New slot is the upward arc from here
      Slot.Up:= Result;

     Result.Next:= Slot.Next;
     LTHigh:= (Slot.Next.HashMarker - 1) SHR 16;
    END;
   Slot.Next:= Result;

   // Update Lookup Table
   For Index:= LTLow to LTHigh do
    FLookupTable[Index]:= Result;

   // Split entry items
{$IFDEF AdaptiveSplit}
   Slot.Range:= 0;
{$ENDIF AdaptiveSplit}
   NewEntryItem:= NIL; OldEntryItem:= NIL;
   EntryItem:= Slot.ItemHead;
   While Assigned(EntryItem) do
    BEGIN
     IF EntryItem.JumboHash >= Result.HashMarker then
      BEGIN
       // Migrate to the new slot
       IF Assigned(NewEntryItem) then
        NewEntryItem.Next:= EntryItem
       else
        Result.ItemHead:= EntryItem;
       NewEntryItem:= EntryItem;
{$IFDEF AdaptiveSplit}
       Range:= EntryItem.JumboHash - Result.HashMarker;
       IF Range > Result.Range then
        Result.Range:= Range;
{$ENDIF AdaptiveSplit}
       IF Assigned(OldEntryItem) then
        OldEntryItem.Next:= EntryItem.Next
       else
        Slot.ItemHead:= EntryItem.Next;
      END
     else
      BEGIN
{$IFDEF AdaptiveSplit}
       Range:= EntryItem.JumboHash - Slot.HashMarker;
       IF Range > Slot.Range then
        Slot.Range:= Range;
{$ENDIF AdaptiveSplit}
       OldEntryItem:= EntryItem;
      END;
     EntryItem:= EntryItem.Next;
    END;

   IF Assigned(NewEntryItem) then
    NewEntryItem.Next:= NIL
   else // When this happens, the split wasn't very effective. We will call back again...
    Result.ItemHead:= NIL;

   IF Assigned(OldEntryItem) then
    OldEntryItem.Next:= NIL
   else // When this happens, the split was overly effective. We will call back again...
    Slot.ItemHead:= NIL;
  END;

 Function TJumboDictionary<TKey, TValue>.TryGetValue(Const Key: TKey; Out Value: TValue): Boolean;
  Var
   HashValue: Cardinal;
   EntrySlot: PEntrySlot;
   EntryItem: PEntryItem;
  BEGIN
   Result:= False;
   HashValue:= Hash(Key);
   EntrySlot:= GetSlot(HashValue);
   EntryItem:= SlotGetItem(EntrySlot, Key);

   IF Assigned(EntryItem) then
    IF (HashValue = EntryItem.JumboHash) AND FComparer.Equals(Key, EntryItem.Key) then
     BEGIN
      Value:= EntryItem.Value;
      Exit(True);
     END;
  END;

 Procedure TJumboDictionary<TKey, TValue>.ValueNotify(Const Value: TValue; Action: TCollectionNotification);
  BEGIN
   IF Assigned(FOnValueNotify) then
    FOnValueNotify(Self, Value, Action);
  END;

 { TJumboDictionary<TKey, TValue>.TPairEnumerator }

 Constructor TJumboDictionary<TKey, TValue>.TPairEnumerator.Create(ADictionary: TJumboDictionary<TKey, TValue>);
  BEGIN
   Inherited Create;

   EntrySlot:= ADictionary.EntryHead;
   // EntryItem:= NIL;
  END;

 Function TJumboDictionary<TKey, TValue>.TPairEnumerator.DoGetCurrent: TPair<TKey, TValue>;
  BEGIN
   Result:= GetCurrent;
  END;

 Function TJumboDictionary<TKey, TValue>.TPairEnumerator.DoMoveNext: Boolean;
  BEGIN
   Result:= MoveNext;
  END;

 Function TJumboDictionary<TKey, TValue>.TPairEnumerator.GetCurrent: TPair<TKey, TValue>;
  BEGIN
   Result.Key:= EntryItem.Key;
   Result.Value:= EntryItem.Value;
  END;

 Function TJumboDictionary<TKey, TValue>.TPairEnumerator.MoveNext: Boolean;
  BEGIN
   Result:= True;
   Repeat
    IF Assigned(EntryItem) then
     EntryItem:= EntryItem.Next
    else // Move to the next slot
     BEGIN
      IF NOT Assigned(EntrySlot) then
       Exit(False);

      EntryItem:= EntrySlot.ItemHead;
      EntrySlot:= EntrySlot.Next;
     END;
   Until Assigned(EntryItem);
  END;

 { TJumboDictionary<TKey, TValue>.TKeyEnumerator }

 Constructor TJumboDictionary<TKey, TValue>.TKeyEnumerator.Create(ADictionary: TJumboDictionary<TKey, TValue>);
  BEGIN
   Inherited Create;

   EntrySlot:= ADictionary.EntryHead;
   // EntryItem:= NIL;
  END;

 Function TJumboDictionary<TKey, TValue>.TKeyEnumerator.DoGetCurrent: TKey;
  BEGIN
   Result:= GetCurrent;
  END;

 Function TJumboDictionary<TKey, TValue>.TKeyEnumerator.DoMoveNext: Boolean;
  BEGIN
   Result:= MoveNext;
  END;

 Function TJumboDictionary<TKey, TValue>.TKeyEnumerator.GetCurrent: TKey;
  BEGIN
   Result:= EntryItem.Key;
  END;

 Function TJumboDictionary<TKey, TValue>.TKeyEnumerator.MoveNext: Boolean;
  BEGIN
   Result:= True;
   Repeat
    IF Assigned(EntryItem) then
     EntryItem:= EntryItem.Next
    else // Move to the next slot
     BEGIN
      IF NOT Assigned(EntrySlot) then
       Exit(False);

      EntryItem:= EntrySlot.ItemHead;
      EntrySlot:= EntrySlot.Next;
     END;
   Until Assigned(EntryItem);
  END;

 { TJumboDictionary<TKey, TValue>.TValueEnumerator }

 Constructor TJumboDictionary<TKey, TValue>.TValueEnumerator.Create(ADictionary: TJumboDictionary<TKey, TValue>);
  BEGIN
   Inherited Create;

   EntrySlot:= ADictionary.EntryHead;
   // EntryItem:= NIL;
  END;

 Function TJumboDictionary<TKey, TValue>.TValueEnumerator.DoGetCurrent: TValue;
  BEGIN
   Result:= GetCurrent;
  END;

 Function TJumboDictionary<TKey, TValue>.TValueEnumerator.DoMoveNext: Boolean;
  BEGIN
   Result:= MoveNext;
  END;

 Function TJumboDictionary<TKey, TValue>.TValueEnumerator.GetCurrent: TValue;
  BEGIN
   Result:= EntryItem.Value;
  END;

 Function TJumboDictionary<TKey, TValue>.TValueEnumerator.MoveNext: Boolean;
  BEGIN
   Result:= True;
   Repeat
    IF Assigned(EntryItem) then
     EntryItem:= EntryItem.Next
    else // Move to the next slot
     BEGIN
      IF NOT Assigned(EntrySlot) then
       Exit(False);

      EntryItem:= EntrySlot.ItemHead;
      EntrySlot:= EntrySlot.Next;
     END;
   Until Assigned(EntryItem);
  END;

 { TJumboDictionary<TKey, TValue>.TValueCollection }

 Constructor TJumboDictionary<TKey, TValue>.TValueCollection.Create(ADictionary: TJumboDictionary<TKey, TValue>);
  BEGIN
   Inherited Create;
   FDictionary:= ADictionary;
  END;

 Function TJumboDictionary<TKey, TValue>.TValueCollection.DoGetEnumerator: TEnumerator<TValue>;
  BEGIN
   Result:= GetEnumerator;
  END;

 Function TJumboDictionary<TKey, TValue>.TValueCollection.GetCount: Integer;
  BEGIN
   Result:= FDictionary.Count;
  END;

 Function TJumboDictionary<TKey, TValue>.TValueCollection.GetEnumerator: TValueEnumerator;
  BEGIN
   Result:= TValueEnumerator.Create(FDictionary);
  END;

 { TJumboDictionary<TKey, TValue>.TKeyCollection }

 Constructor TJumboDictionary<TKey, TValue>.TKeyCollection.Create(ADictionary: TJumboDictionary<TKey, TValue>);
  BEGIN
   Inherited Create;
   FDictionary:= ADictionary;
  END;

 Function TJumboDictionary<TKey, TValue>.TKeyCollection.DoGetEnumerator: TEnumerator<TKey>;
  BEGIN
   Result:= GetEnumerator;
  END;

 Function TJumboDictionary<TKey, TValue>.TKeyCollection.GetCount: Integer;
  BEGIN
   Result:= FDictionary.Count;
  END;

 Function TJumboDictionary<TKey, TValue>.TKeyCollection.GetEnumerator: TKeyEnumerator;
  BEGIN
   Result:= TKeyEnumerator.Create(FDictionary);
  END;

END.
